import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 刘远望
 * Date: 2025-05-30
 * Time: 20:29
 */
//力扣30 哈希表+count
public class Solution {
    //哈希表
    public List<Integer> findSubstring1(String s, String[] words) {
        Map<String, Integer> hash2 = new HashMap<>();//放words中单词出现的次数
        for (String word : words) {
            hash2.put(word, hash2.getOrDefault(word, 0) + 1);//将words的单词放入哈希表
        }

        int len = words[0].length();//一个单词的长度 也是窗口移动一次跳过的长度
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {//总循环的次数
            Map<String, Integer> hash1 = new HashMap<>();//放s中分割字符串出现的频次
            for (int left = i, right = i; right + len <= s.length(); right += len) {
                String in = s.substring(right, right + len);
                hash1.put(in, hash1.getOrDefault(in, 0) + 1);//进窗口

                if (right - left + 1 > len * words.length) {//判断
                    String out = s.substring(left, left + len);
                    hash1.put(out, hash1.get(out) - 1);
                    if (hash1.get(out) == 0) {
                        hash1.remove(out);//频次为0要删除以免影响结果更新判断
                    }
                    left += len;//出窗口
                }
                if (hash1.equals(hash2)) {
                    list.add(left);//更新结果
                }
            }
        }
        return list;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> hash2 = new HashMap<>();//放words中单词出现的次数
        for (String word : words) {
            hash2.put(word, hash2.getOrDefault(word, 0) + 1);//将words的单词放入哈希表
        }

        int len = words[0].length();//一个单词的长度 也是窗口移动一次跳过的长度
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < len; i++) {//总循环的次数
            Map<String, Integer> hash1 = new HashMap<>();//放s中分割字符串出现的频次
            for (int left = i, right = i, count = 0; right + len <= s.length(); right += len) {
                String in = s.substring(right, right + len);
                hash1.put(in, hash1.getOrDefault(in, 0) + 1);//进窗口
                if (hash1.get(in) <= hash2.getOrDefault(in, 0)) {
                    count++;//维护count
                }

                if (right - left + 1 > len * words.length) {//判断
                    String out = s.substring(left, left + len);
                    if (hash1.get(out) <= hash2.getOrDefault(out, 0)) {
                        count--;//维护count
                    }
                    hash1.put(out, hash1.get(out) - 1);
                    left += len;//出窗口
                }
                if (count == words.length) {
                    list.add(left);//更新结果(count)
                }
            }
        }
        return list;
    }
}
